In many communication and storage systems, variations in signal strength cause problems in detection. One such example is a holographic storage system.
FIG. 1a is a block diagram of a write apparatus 102. Encoder 112 accepts as its input digital data in the form of units known as datawords 110. The input data is encoded to a form suitable for recording and output from encoder 112 in the form of units known as codewords 114. The codewords may input to other write apparatus circuitry 116, which outputs a signal which controls the actual recording of the data.
FIG. 1b is a block diagram of a read apparatus 108. The analog signal from the read channel is input to analog to digital converter (ADC) 122 of read apparatus 108, which outputs a digital signal comprising units known as samples 124. Each sample represents the intensity of the analog signal at one point. A series of samples is represented in 124. A plurality of samples 124 are grouped together to form a sequence 125 of samples. Sequences 125 are input to detector 126, which reconstructs the original data which were input for recording, based on samples 124. The reconstructed codewords 128 are output from detector 126. The reconstructed datawords 132 are output from decoder 130. In practice, the detector and decoder may be combined.
FIG. 1c depicts the application of read apparatus 108 of FIG. 1b and write apparatus 102 of FIG. 1a to a holographic storage device. The holographic storage device accepts its input from write apparatus 102 of FIG. 1a, which accepts as its input the data to be recorded, encodes the data and converts it to a signal which controls spatial light modulator (SLM) 104. SLM 104, which is illuminated by laser light source 103, converts the laser light into an optical signal 105 representing the input data. The interference pattern between signal 105 and a reference beam from reference beam source 101 is recorded in holographic medium 106. Charge coupled device (CCD) array 109 accepts as its input an optical signal 107 output from holographic medium 106 and outputs an analog electrical signal representing the illumination intensity of each pixel in the CCD. This signal is output from the holographic storage device to read apparatus 108 of FIG. 1b, which converts the analog signal into digital signals, and decodes the signals to recover the recorded data.
In a typical holographic storage application, a codeword bit value of 1 is written using an on or illuminated pixel and a bit value of 0 is written using an off or unilluminated pixel. Of course, the opposite illumination arrangement could be used instead. The codewords are written as arrays, each having the same dimensions, on the SLM. For example, a codeword having length 12 may be written as a 3 by 4 array. A sequence of codewords is rastered across the SLM. For example, if each codeword is written as a 3 by 4 array, then the first three rows of the SLM are first filled in by a sequence of 3 by 4 arrays, then the next three rows, and so on, until the entire SLM is filled in.
When written, each pixel is illuminated with a fully on or fully off light source. When a codeword is read from the holographic memory, the light received by CCD camera 109 is not free from distortion. Typically, pixels of the CCD receive neither fully on nor fully off illumination, but rather partially on and partially off illumination. The samples output from ADC 122 reflect this partial illumination. Detector 126 must estimate the actual codeword being output based on the sequence of samples received from ADC 122.
A well-known detection system is threshold detection. Threshold detection means that a threshold value for samples is established. All samples greater in value than the threshold are considered to be 1's and all samples lesser in value than the threshold are considered to be 0's. Threshold detection has two main problems. First, the threshold must be computed. Typically, the values of a large number of samples must be averaged in order to compute the threshold. This produces a large amount of computational overhead which decreases the performance and increases the cost of the detection system. Second, noise in the optical or electrical signals significantly increases the error rate of the detection system. An increased error rate requires a more complex error correction scheme, which raises the cost and lowers the performance of the detection system. If the error rate becomes too high, it may be impossible to correct all the errors. The result is a loss of data, which could be catastrophic. What is required is a detection system with decreased computational overhead and more robust noise performance.
One solution to the problems inherent in threshold detection is the use of balanced codes. A balanced code is one in which each codeword is balanced--it contains exactly the same number of 1's as 0's. Use of a balanced code eliminates the need to compute a threshold. Since the number of 1's and 0's is balanced, the brighter 50% of the samples are considered to be 1's and the dimmer 50% of the samples are considered to be 0's. In addition, the minimum distance, the minimum number of bits by which two distinct codewords differ, is 2. In a balanced code, a change in just one bit yields an invalid codeword because the result is unbalanced. To remain in balance, at least two bits must change. The larger the minimum distance, the easier it is to distinguish among distinct codewords. The minimum distance of a balanced code can be made larger if desired.
Balanced codes belong to a general class of codes known as DC free codes. Each codeword in a DC free code is not necessarily balanced, but the imbalance over a code sequence of arbitrary length is bounded. DC free codes have advantages similar to those of balanced codes.
Problems arise in the use of balanced or DC free codes. Prior art detection schemes are not complete. If the detected word is not a valid codeword, current detection schemes cannot, by themselves, handle the error. While this may be adequate for storage devices with very clean output signals, it is not adequate for holographic storage devices, or any other devices which have relatively noisy and distorted output signals. Furthermore, current balanced code detection schemes are inefficient in that they require considerable sorting, which increases the cost and decreases the performance of the detector.